package acwing.算法题;/**
 * @author： li
 * @date： 2022-03-10 18:54
 * @version 1.0
 */

import java.util.Scanner;

/**
 算法
 (递推) O(n)O(n)
 这题的数据范围很小，我们直接模拟即可。
 当数据范围很大时，就需要采用其他方式了，可以参考 求解斐波那契数列的若干方法 。

 用两个变量滚动式得往后计算，aa 表示第 n−1n−1 项，bb 表示第 nn 项。
 则令 c=a+bc=a+b 表示第 n+1n+1 项，然后让 a,ba,b 顺次往后移一位。

 时间复杂度分析
 总共需要计算 nn 次，所以时间复杂度是 O(n)O(n) 。
 */
public class 斐波那契数列_递推 {
    static int Fibonacci(int n) {
        int a = 0, b = 1;
        while (n-->0) {
            int c = a + b;
            a = b;
            b = c;
        }
        return a;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n= sc.nextInt();
        int ans = Fibonacci(n);
        System.out.println(ans);
        sc.close();
    }
}
